package exer3;

/**
 * @author tongchen
 * @create 2022-10-13 15:07
 */
public class ListNode {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode9 = new ListNode(0);
        ListNode listNode5 = new ListNode(0);
        ListNode listNode6 = new ListNode(-3);
        ListNode listNode7 = new ListNode(6);
        ListNode listNode8 = new ListNode(0);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        listNode5.next=listNode6;
        listNode6.next=listNode7;
        listNode7.next=listNode8;
        listNode8.next=listNode9;
        System.out.println(Partition.partition(listNode1, 5));
    }
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
 class Partition {
    public static ListNode partition(ListNode pHead, int x) {
        //先处理链表为空的情况
        if(pHead==null){
            return null;
        }
        // write code here
        ListNode head1=new ListNode(-1);
        ListNode head2=new ListNode(-1);
        ListNode cur1=pHead;
        ListNode cur2=head1;
        ListNode cur3=head2;
        while(cur1!=null){
            if(cur1.val<x){
                cur2.next=cur1;
                cur1=cur1.next;
                cur2=cur2.next;
            }
            else{
                cur3.next=cur1;
                cur1=cur1.next;
                cur3=cur3.next;
            }
        }

        if(head1.next==null){
            return head2.next;
        }
        if(head2.next==null){
            return head1.next;
        }
        //将head2放到head1之后
        cur2.next=head2.next;
        return head1.next;

    }

     @Override
     public String toString() {
         return "Partition{}";
     }
 }
